/*
 * @lc app=leetcode.cn id=222 lang=cpp
 *
 * [222] 完全二叉树的节点个数
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
  int countNodes(TreeNode* root)
  {
    int H = 0;
    for (TreeNode* tmp = root; tmp != nullptr; tmp = tmp->left)
      ++H;
    if (H < 2)
      return H;
    
    int L = 1 << (H - 1), R = (1 << H) - 1;
    int mask = 1 << (H - 2);// 第一层最高位看成1
    while (L < R) {
      int M = (L + R + 1) / 2; // 由于第M个节点存在时L = M，所以+1取下一位
      TreeNode* tmp = root;
      for (int path = mask; path != 0; path >>= 1) {
        if (path & M)// 1 ==> 右
          tmp = tmp->right;
        else
          tmp = tmp->left;
      }
      if (tmp)
        L = M;
      else
        R = M - 1;
    }
    return R;
  }
};
// @lc code=end
